#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    map<char, string> m;
    Solution()
    {
        m['2'] = "abc"; m['3'] = "def"; m['4'] = "ghi"; m['5'] = "jkl";
        m['6'] = "mno"; m['7'] = "pqrs"; m['8'] = "tuv"; m['9'] = "wxyz";
    }
    vector<string> letterCombinations(string digits)
    {
        vector<string> ret;
        if (digits.size() == 0)
        {
            return ret;
        }
        Combinations(0, ret, digits, "");
        return ret;
    }

    void Combinations(int len, vector<string>& ret, string digits, string str)
    {
        if (len == digits.size())
        {
            ret.push_back(str);
            return;
        }
        for (int i = 0; i < m[digits[len]].size(); i++)
        {
            Combinations(len + 1, ret, digits, str + m[digits[len]][i]);
        }
    }
};

int main()
{
    Solution T;
    vector<string> a=T.letterCombinations("23");
    return 0;
}